package top100.hash;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/21 8:47
 * @description:
 */
public class Solution560 {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int preSum = 0; // 前缀和，无需数组，用变量累加即可
        HashMap<Integer, Integer> preSumCount = new HashMap<>();

        // 初始化：前缀和为0的情况出现1次（处理子数组从0开始的情况）
        preSumCount.put(0, 1);

        for (int num : nums) {
            preSum += num; // 计算当前前缀和

            // 核心：如果存在preSum - k，说明存在子数组和为k
            if (preSumCount.containsKey(preSum - k)) {
                count += preSumCount.get(preSum - k);
            }

            // 将当前前缀和加入哈希表，次数+1
            preSumCount.put(preSum, preSumCount.getOrDefault(preSum, 0) + 1);
        }

        return count;
    }

    public static void main(String[] args) {
        Solution560 solution = new Solution560();
        // 测试用例：[1,1,1]，k=2 应返回2
        System.out.println(solution.subarraySum(new int[]{1, 1, 1}, 2)); // 输出2
    }
}
